package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 给表达式添加运算符282.java
 * @createTime 2023年01月07日 14:07:00
 */
public class 给表达式添加运算符282 {
	List<String> result = new ArrayList<>();

	public List<String> addOperators(String num, int target) {
		backTrace(num, target, 0, 0, "",0);
		return result;
	}

	public void backTrace(String num, int target, int curIndex, long curSum, String express, long preAdd) {
		if (curSum == target && curIndex == num.length()) {
			result.add(express);
			return;
		}

		for (int i = curIndex; i < num.length(); i++) {
			//当前数
			String next = num.substring(curIndex, i + 1);
			long cur = Long.parseLong(next);
			//如果是首位
			if (i == 0 || num.charAt(i)=='0') {
				backTrace(num, target, i + 1, cur,express  + cur, cur);
			} else {
				backTrace(num, target, i + 1, curSum + cur, express + "+" + next,cur);
				backTrace(num, target, i + 1, curSum - cur, express + "-" + next,cur);
				backTrace(num, target, i + 1, curSum - preAdd + cur * preAdd, express + "*" + next,cur);
			}
			if (cur==0){
				return;
			}
		}
	}
}
